/*
练习15-6 教室安排问题
分数 25
作者 陈越
单位 浙江大学

假设有 n
个俱乐部来申请使用活动教室，每个俱乐部的活动都有一个计划开始的时间和结束的时间。要求为每项活动安排可以使用的教室，保证所有活动在安排上不能有冲突（即前一个活动的结束时间不迟于后一个活动的开始时间），问最少需要多少间教室？
函数接口定义：

int ActivityScheduling(Activities a, int n);

其中 Activities 类型的定义如下：

typedef struct ActivityNode *Activities;
struct ActivityNode {
    int start;  // 开始时间
    int finish; // 结束时间
};

函数接口定义中，a 是存放活动集合的数组，共有 n 个活动，并且按 start
的非递减序存放。其中 a[0]  是一个虚设的活动，其开始、结束时间和权重均为
0。要求函数 ActivityScheduling 返回最少需要的房间数量。

输入样例：

8
1 2
3 4
5 6
1 9
7 20
10 11
12 13
13 14

输出样例：

2
*/
#include <stdio.h>
#include <stdlib.h>

typedef struct ActivityNode *Activities;
struct ActivityNode {
    int start;  /* 开始时间 */
    int finish; /* 结束时间 */
};

typedef enum { false, true } bool;

int ActivityScheduling(Activities a, int n);

int CmpStart(const void *a, const void *b) {
    return (((const struct ActivityNode *)a)->start >
            ((const struct ActivityNode *)b)->start)
               ? 1
               : -1;
}

int main(void) {
    Activities a;
    int n, i;

    scanf("%d", &n);
    a = (Activities)malloc(sizeof(struct ActivityNode) * (n + 1));
    a[0].finish = 0; /* a[0] 是一个虚设的活动，其结束时间为 0 */
    a[0].start = 0;
    for (i = 1; i <= n; i++) {
        scanf("%d %d", &a[i].start, &a[i].finish);
    }
    qsort(a, n + 1, sizeof(struct ActivityNode), CmpStart);
    printf("%d", ActivityScheduling(a, n));

    return 0;
}

/* 你的代码将被嵌在这里 */
int ActivityScheduling(Activities a, int n) {
    int *endTimes = (int *)malloc(sizeof(int) * n); // 分配结束时间数组
    int roomCount = 0; // 教室数量

    for (int i = 1; i <= n; i++) {
        bool assigned = false;
        for (int j = 0; j < roomCount; j++) {
            if (a[i].start >= endTimes[j]) {
                endTimes[j] = a[i].finish; // 更新教室的结束时间
                assigned = true;
                break;
            }
        }
        if (!assigned) {
            endTimes[roomCount++] = a[i].finish; // 分配新的教室
        }
    }

    free(endTimes); // 释放结束时间数组
    return roomCount; // 返回教室数量
}